Search results for " 03D15"

showing 2 items of 2 documents

Topological Logics with Connectedness over Euclidean Spaces

2013

We consider the quantifier-free languages, Bc and Bc °, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of R n ( n ≥ 2) and, additionally, over the regular closed semilinear sets of R n . The resulting logics are examples of formalisms that have recently been proposed in the Artificial Intelligence literature under the rubric Qualitative Spatial Reasoning. We prove that the satisfiability problem for Bc is undecidable over the regular closed semilinear sets in all dimensions greater than 1,…

FOS: Computer and information sciencesComputer Science - Logic in Computer ScienceGeneral Computer ScienceUnary operationClosed setLogicSocial connectedness0102 computer and information sciencesTopological space68T30 (Primary) 03D15 68Q17 (Secondary)Topology01 natural sciencesTheoretical Computer ScienceMathematics - Geometric TopologyEuclidean geometryFOS: Mathematics0101 mathematicsMathematicsI.2.4; F.4.3; F.2.2Discrete mathematicsI.2.4010102 general mathematicsGeometric Topology (math.GT)Predicate (mathematical logic)Undecidable problemLogic in Computer Science (cs.LO)Computational Mathematics010201 computation theory & mathematicsF.4.3F.2.2Boolean satisfiability problemACM Transactions of Computational Logic
researchProduct

Exact quantum algorithms have advantage for almost all Boolean functions

2014

It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.

FOS: Computer and information sciencesNuclear and High Energy Physics81P68 03D15Parity functionBoolean circuitGeneral Physics and AstronomyFOS: Physical sciencesBoolean algebras canonically definedComputational Complexity (cs.CC)Theoretical Computer ScienceCombinatoricsBoolean expressionBoolean functionMathematical PhysicsComputer Science::DatabasesMathematicsDiscrete mathematicsSymmetric Boolean functionQuantum PhysicsProduct termComputer Science::Information RetrievalStatistical and Nonlinear PhysicsComputer Science - Computational ComplexityComputational Theory and MathematicsMaximum satisfiability problemQuantum Physics (quant-ph)
researchProduct